// 全排列：指的是从n个不同元素中取出m个元素，按照一定的顺序排成一列，当(m = n)时的排列情况
// 假设有三个不同的元素A、B、C，那么它们的全排列就是所有可能的排列方式，即ABC、ACB、BAC、BCA、CAB、CBA，共6种。


// 回溯法
// 回溯法是一种通过尝试所有可能的组合来解决问题的算法。
// 对于全排列问题，回溯法会逐步构建排列，当构建出一个完整的排列后，将其记录下来，然后回溯到上一步，尝试其他可能的组合。
function permute(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);  // 标记每个元素是否已经在当前排列中使用过

  // backtrack 函数接受一个 path 参数，表示当前已经构建的排列
  function backtrack(path) {
    // 停止条件
    // 当路径的长度等于数组的长度时，说明已经得到一个完整的排列
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      // 如果该元素已经在路径中，跳过
      if (used[i]) continue;
      // 选择当前元素
      path.push(nums[i]);
      used[i] = true;
      // 递归生成下一个位置的排列
      backtrack(path);
      // 回溯，撤销选择
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

// 测试示例
const nums = [1, 2, 3];
console.log(permute(nums));
